/*
  强哥的爆炸异术
  题目背景
    Dutchland 对 Russland 发起了突然入侵，Russland 反应不及，瞬间丢失了大片领土。
    Russland 内务人民委员贝利亚受命组织敌后游击战。
    强哥作为工作团成员，主要负责协调物资的敌后供给工作。
  题目描述
    敌后游击队的常见任务之一就是炸掉 Dutchland 的铁路线，以切断后勤补给。
    这样的铁路线有 K 条。
    强哥的手中有 N 块长方形的 TNT 炸药，其中第 i 块是 Hi × Wi 的方格组成的长方形。
    他现在需要把这些炸药分给游击队员们。
    每条铁路线都应当被分到一块相同大小的正方形炸药。

    强哥的数学很好，但是贝利亚每天大晚上都会带着他去 Kremlin 找慈父同志喝伏特加，
    所以他实在是没办法，把分配炸药的任务交给了你。
  输入格式
    第一行包含两个整数 N 和 K。(1 ≤ N, K ≤ 10^5)。
    以下 N 行每行包含两个整数 Hi 和 Wi。(1 ≤ Hi, Wi ≤ 10^4)。
    输入保证每处铁路线都能被 TNT 炸。
  输出格式
    输出切出的炸药最大的尺寸。分出去的每个炸药应当是 x×x 的方格组成的正方形，输出 x 即可。
  输入数据 1
    2 10
    6 5
    5 6
  输出数据 1
    2
*/

#include <bits/stdc++.h>

using namespace std;

/*
  思路:
    通常采用二分答案算法的话, 需要首先明确 2 个核心问题:
      1) 答案的取值范围(区间)，即确定区间的最大值和最小值
      2) 判断某个答案是否满足题意(条件)的判定方法
    解答本题时，先明确出这 2 个问题:
      1）答案的取值范围(区间)
          区间的最小值: 1;
          区间的最大值: "假设每块长方形的 TNT 炸药只获得一块最大的正方形炸药，n 块长方形中能获得的最大的正方形炸药的边长";
      2) 判断某个答案是否满足题意的判定方法:
          遍历每块长方形炸药，计算每块能分出几块边长为 x(答案) 的正方形，并进行累加；
          如果累加值大于等于 k，则该答案满足题目要求；
          否则，答案不能满足题目要求。
*/

int n, k;
int a[100010][3] = {}; // a[i][1] 表示发起第 i 块炸药的长，a[i][2] 表示发起第 i 块炸药的宽 (其中 i > 0)
int s = 1;  // s(start) 表示二分答案算法实现中进行二分查找时的开始边界(左边界)
int e = 0;  // e(end)   表示二分答案算法实现中进行二分查找时的结束边界(右边界)

// 该函数用来判断输入 x(表示答案，即得到的正方形炸药的边长) 是否满足条件(题目要求)
bool check(int x) {
    int sum = 0;  // 得到的边长为 x 的正方形炸药的个数
    int c = 0;
    int kuan = 0;

    for (int i = 1; i <= n; i++) {
            c = a[i][1] / x;
            kuan = a[i][2] / x;
            sum = sum + (c * kuan);
    }
    if (sum >= k) {
        return true;
    } else {
        return false;
    }
}

int main() {

    cin >> n >> k;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 2; j++){
            cin >> a[i][j];
        }

        int x = min(a[i][1], a[i][2]);
        e = max(x, e);  // 区间的最大值: "假设每块长方形炸药只获得一块最大的正方形炸药，n 块炸药中能获得最大的正方形炸药的边长";
    }

    /*
      用二分查找法，在答案的区间范围内，查找满足题目要求的最大值
      注意:
        特别技巧: 我们在编码时，要保证区间的最大值 e 一定大于等于 区间的最小值 s
                 这样就可以保证一定会进行一次循环处理!
    */
    int ans = 0;
    while (s <= e) {
        int mid = (s + e) / 2;
        if (check(mid)) {
            ans = mid;
            s = mid + 1;  // 由于需要答案尽可能地大，所以我们进一步从 mid 的右半区间进行查找
        } else {
            e = mid - 1;  // mid 不满足题目要求，从 mid 的左半区间进行查找
        }
    }

    cout << ans;

    return 0;
}